package lc.q300_350;

import java.util.*;

public class Q345 {

    public static void main(String[] args) {
        Q345 q345 = new Q345();
        System.out.println(q345.reverseVowels2("haweti"));
    }

    public String reverseVowels2(String s) {
        char[] chars = s.toCharArray();
        Set<Character> set = new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
        // 左右指针法
        int i = 0, j = s.length() - 1;
        while (i < j) {
            while (i < s.length() && !set.contains(s.charAt(i))) {
                i ++;
            }
            while (j >= 0 && !set.contains(s.charAt(j))) {
                j --;
            }
            if (i < j) {
                chars[i] = s.charAt(j);
                chars[j] = s.charAt(i);
                i ++;
                j --;
            }
        }
        return new String(chars);
    }

    public String reverseVowels(String s) {
        char[] chars = s.toCharArray();
        Set<Character> set = new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
        // list记录元字符
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < chars.length; i++) {
            if (set.contains(chars[i])) {
                deque.addLast(i);
            }
        }
        while (!deque.isEmpty()) {
            Integer last = deque.pollLast();
            Integer first = deque.pollFirst();
            if (last != null && first != null) {
                chars[first] = s.charAt(last);
                chars[last] = s.charAt(first);
            }
        }
        return new String(chars);
    }
}
